﻿// RopeNode.cs
//
// Author: Luoyingliang
// Email: 731984870@qq.com
// 
// Copyright (c) 2018 Team Acoris
// Permission is hereby granted, free of charge, to any person obtaining a copy
// of this software and associated documentation files (the "Software"), to deal
// in the Software without restriction, including without limitation the rights
// to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
// copies of the Software, and to permit persons to whom the Software is
// furnished to do so, subject to the following conditions:
//
// The above copyright notice and this permission notice shall be included in
// all copies or substantial portions of the Software.
//
// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
// OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
// THE SOFTWARE.

using System;
using System.Collections.Generic;
using System.Text;

namespace Acoris.Text
{
    using System.Collections;
    using static Acoris.Utils.ValueRangeChecker;

    // notice that:
    // this class didn't written in thread-safe mode.all member method in this class
    // run on multi-thread mode we could not guarantee that will return a expected 
    // value

    /// <summary>
    /// represents a rope data-structure
    /// </summary>
    public sealed class Rope : IComparable, IComparable<string>, IEnumerable<char>, IEnumerable, IEquatable<string> {

        #region Enumerator

        /// <summary>
        /// 
        /// </summary>
        public struct RopeEnumerator : IEnumerator<char>
        {
            private RopeNode m_node;
            private RopeNode m_root;
            private char     m_char;
            private int      m_index;
            private int      m_length;

            internal RopeEnumerator(RopeNode node) {
                CheckNullParameter(node);
                m_node = node;
                m_root = node;
                m_char = char.MaxValue;
                m_index = -1;
                m_length = m_node.length;
            }

            /// <summary>
            /// 
            /// </summary>
            public char Current { get { return m_char; } }

            /// <summary>
            /// 
            /// </summary>
            object IEnumerator.Current { get { return m_char; } }

            /// <summary>
            /// 
            /// </summary>
            public void Dispose() {
                m_node = null;
                m_char = char.MinValue;
            }

            public bool MoveNext() {

                return m_index < m_length;
            }

            public void Reset() {
                throw new NotImplementedException();
            }
        }

        #endregion

        internal RopeNode root;
        private int length;

        /// <summary>
        /// construct a empty rope
        /// </summary>
        public Rope() {
            root = RopeNode.EmptyNode;
            length = 0;
        }

        /// <summary>
        /// construct a rope with specific string 
        /// </summary>
        /// <param name="text">source text</param>
        public Rope(string text) : this(text.ToCharArray()) { }

        /// <summary>
        /// construct a rope with specific array
        /// </summary>
        /// <param name="array">source array</param>
        public Rope(char[] array) : this(array, 0, array.Length) { }

        /// <summary>
        /// construct a rope with specific array, index and count
        /// </summary>
        /// <param name="array">source array</param>
        /// <param name="index">the index of source array</param>
        /// <param name="count">amount of source array</param>
        ///         /// <exception cref="ArgumentNullException">array is null</exception>
        /// <exception cref="IndexOutOfRangeException">
        /// index was a negative value or large than the count of array
        /// </exception>
        public Rope(char[] array, int index, int count) {
            if (array == null) {
                throw new ArgumentNullException("array cannot be null");
            }

            if (index < 0 || index + count < array.Length) {
                throw new IndexOutOfRangeException("index out of range");
            }
            root = RopeNode.CreateFromArray(array, index, count);
            length = count;
        }

        /// <summary>
        /// insert specific range content to current node
        /// </summary>
        /// <param name="array">source array</param>
        /// <param name="arrayIndex">where the index of array start</param>
        /// <param name="count">the amount of chars</param>
        /// <exception cref="ArgumentNullException">array is null</exception>
        /// <exception cref="IndexOutOfRangeException">
        /// index was a negative value or large than the count of array
        /// </exception>
        public void InsertRange(char[] array, int arrayIndex, int count) {
            InsertRange(0, array, arrayIndex, count);
        }

        /// <summary>
        /// 
        /// </summary>
        /// <param name="index"></param>
        /// <param name="array"></param>
        /// <param name="arrayIndex"></param>
        /// <param name="count"></param>
        public void InsertRange(int index, char[] array, int arrayIndex, int count) {
            if (array == null) {
                throw new ArgumentNullException("array cannot be null");
            }

            if (arrayIndex < 0 || arrayIndex + count < array.Length) {
                throw new IndexOutOfRangeException("arrayIndex out of range");
            }

            if (index < 0 || index > this.length) {
                throw new IndexOutOfRangeException("index out of range");
            }

            if (index == 0) {
                var newElement = RopeNode.CreateFromArray(array,arrayIndex,count);
                newElement.Concat(this.root);
                this.root = newElement;
                this.length = this.root.length;
            } else if (index == this.length - 1) {
                var newElement = RopeNode.CreateFromArray(array,arrayIndex,count);
                this.root.Concat(newElement);
                this.length += newElement.length;
            }
            else {
                var newElement = RopeNode.CreateFromArray(array,arrayIndex,count);
                var before = root;
                var after = root.Split(index);
                this.root = RopeNode.Concat(before, RopeNode.Concat(newElement, after));
                this.length += newElement.length;
            }
        }

        /// <summary>
        /// insert specific string text to current rope
        /// </summary>
        /// <param name="text">the source string</param>
        /// <exception cref="ArgumentNullException">text was null</exception>
        public void Insert(string text) {

            if (text == null) {
                throw new ArgumentNullException("text cannot be null");
            }

            if (text.Length == 0) {
                return;
            }

            var array = text.ToCharArray();
            InsertRange(array, 0, array.Length);

        }

        /// <summary>
        /// 
        /// </summary>
        /// <param name="index"></param>
        /// <param name="count"></param>
        public string GetString(int index, int count) {

            if (index < -1) {
                throw new ArgumentOutOfRangeException("index cannot be a negative value");
            }

            if (index + count > root.length) {
                throw new IndexOutOfRangeException("index out of range");
            }

            if (index == root.length - 1 || count == 0) {
                return string.Empty;
            }

            var builder = new StringBuilder();
            GetString(root, builder, index, count);
            return builder.ToString(); ;
        }

        //recursive get string with index and count
        static void GetString(RopeNode node, StringBuilder builder, int index, int count) {
            if (node.height == 0) {
                node.AppendString(builder, index, count);
            }
            else {
                var left = node.left;
                if (index < left.length) {

                    // append left node 
                    GetString(left,
                                builder,
                                index,
                                Math.Min(count, left.length));

                    // if index was in the left node but after append. count large than left node.
                    // then we also need append the right node to StringBuilder
                    // 
                    if (count > left.length) {
                        GetString(node.right, builder, index - left.length, count - left.length);
                    }
                }
                else {
                    GetString(node.right, builder, index - left.length, count);
                }
            }
        }

        // recursive get string
        static void GetString(RopeNode node, StringBuilder builder) {
            if (node.height == 0) {
                builder.Append(node.contents, 0, node.length);
            }
            else {
                GetString(node.left, builder);
                if (node.right != null) {
                    GetString(node.right, builder);
                }
            }
        }

        /// <summary>
        /// get this node's all string
        /// </summary>
        /// <returns></returns>
        public string GetString() {
            var builder = new StringBuilder();
            GetString(this.root, builder);
            return builder.ToString();
        }

        /// <summary>
        /// 
        /// </summary>
        /// <param name="character"></param>
        /// <param name="index"></param>
        /// <param name="count"></param>
        /// <returns></returns>
        public int IndexOf(char character, int index, int count) {
            return int.MaxValue;
        }

        /// <summary>
        /// 
        /// </summary>
        /// <param name="array"></param>
        /// <param name="index"></param>
        /// <param name="count"></param>
        /// <returns></returns>
        public Rope Replace(char[] array, int index, int count) {

            return null;
        }

        /// <summary>
        /// 
        /// </summary>
        /// <param name="character"></param>
        /// <returns></returns>
        public Rope Replace(char character) {
            return null;
        }

        /// <summary>
        /// 
        /// </summary>
        /// <param name="characters"></param>
        /// <returns></returns>
        public Rope Replace(params char[] characters) {
            return null;
        }

        /// <summary>
        /// 
        /// </summary>
        /// <param name="newElement"></param>
        /// <param name="index"></param>
        /// <param name="count"></param>
        /// <returns></returns>
        public Rope Replace(Rope newElement, int index, int count) {
            return null;
        }

        /// <summary>
        /// 
        /// </summary>
        /// <param name="obj"></param>
        /// <returns></returns>
        public int CompareTo(object obj) {
            throw new NotImplementedException();
        }

        /// <summary>
        /// 
        /// </summary>
        /// <returns></returns>
        public object Clone() {
            throw new NotImplementedException();
        }

        /// <summary>
        /// 
        /// </summary>
        /// <param name="other"></param>
        /// <returns></returns>
        public int CompareTo(string other) {
            throw new NotImplementedException();
        }

        /// <summary>
        /// 
        /// </summary>
        /// <returns></returns>
        public IEnumerator<char> GetEnumerator() {
            return new RopeEnumerator(this.root
                                          .Clone());
        }

        /// <summary>
        /// 
        /// </summary>
        /// <returns></returns>
        IEnumerator IEnumerable.GetEnumerator() {
            return new RopeEnumerator(this.root
                                          .Clone());
        }

        /// <summary>
        /// 
        /// </summary>
        /// <param name="other"></param>
        /// <returns></returns>
        public bool Equals(string other) {
            throw new NotImplementedException();
        }

        /// <summary>
        /// set a char to specific position
        /// </summary>
        /// <param name="node">destination node</param>
        /// <param name="offset">offset</param>
        /// <param name="value">value</param>
        internal static void SetChar(RopeNode node, int offset, char value) {

            if (node.height == 0) {
                node.contents[offset] = value;
            }
            else {
                var left = node.left;
                if (offset < left.length) {
                    SetChar(left, offset, value);
                }
                else {
                    SetChar(node.right, offset - left.length, value);
                }
            }
        }

        /// <summary>
        /// get the specific position char
        /// </summary>
        /// <param name="node">destination node</param>
        /// <param name="offset">offset</param>
        /// <returns>return the specific position char</returns>
        internal static char GetChar(RopeNode node, int offset) {
            if (node.height == 0) {
                return node.contents[offset];
            }
            else {
                var left = node.left;
                if (offset < left.length) {
                    return GetChar(left, offset);
                }
                else {
                    return GetChar(node.right, offset - left.length);
                }
            }
        }

        /// <summary>
        /// gets or sets a value in specific position
        /// this method run in O(lg N)
        /// </summary>
        /// <param name="index">index</param>
        /// <exception cref="IndexOutOfRangeException">index out of range</exception>
        /// <returns>
        /// return a value that value is the specific position's element
        /// </returns>
        public char this[int index] {
            get {
                if (index >= root.length) {
                    throw new IndexOutOfRangeException("index");
                }
                return GetChar(root, index);
            }
            set {
                if (index >= root.length) {
                    throw new IndexOutOfRangeException("index");
                }
                SetChar(root, index, value);
            }
        }

        /// <summary>
        /// 
        /// </summary>
        /// <param name="obj"></param>
        /// <returns></returns>
        public override bool Equals(object obj) {
            return base.Equals(obj);
        }

        /// <summary>
        /// 
        /// </summary>
        /// <returns></returns>
        public override int GetHashCode() {
            return base.GetHashCode();
        }

        /// <summary>
        /// 
        /// </summary>
        /// <returns></returns>
        public override string ToString() {
            return base.ToString();
        }
    }
}